Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3},

  1.    1
  2.     \
  3.      2
  4.     /
  5.    3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public List<Integer> postorderTraversal(TreeNode root) {
  12.     List<Integer> res = new ArrayList<Integer>();
  14.     if (root == null)
  15.       return res;
  17.     Stack<TreeNode> s1 = new Stack<TreeNode>();
  18.     Stack<TreeNode> s2 = new Stack<TreeNode>();
  20.     s1.push(root);
  22.     while (!s1.isEmpty()) {
  23.       TreeNode node = s1.pop();
  24.       s2.push(node);
  26.       if (node.left != null)
  27.         s1.push(node.left);
  29.       if (node.right != null)
  30.         s1.push(node.right);
  31.     }
  33.     while (!s2.isEmpty())
  34.       res.add(s2.pop().val);
  36.     return res;
  37.   }
  38. }